/** 堆代码实现
 * 面向过程
 * 基于数组
 * */

/** 大顶堆 */
class Heap {
  constructor() {
    this.data = new Array().fill(100);
    this.cnt = 0; // 前几个元素是堆，类似于tail。注意下标是从0开始
  }
  top() {
    return this.data[0];
  }
  size() {
    return this.cnt;
  }
  /** 插入
   * 插入一个值，并调整位置，形成符合条件的堆（大顶堆） */
  push(val) {
    this.data[this.cnt++] = val; // 插入到最后
    /** -------- 调整 -------- */
    let ind = this.cnt - 1; // 当前值下标
    while(ind && this.data[ind] > this.data[Math.floor((ind - 1) / 2)]) { // 如果当前值比父节点小，就网上浮。父节点下标是 Math.floor((ind - 1) / 2)
      // 交换位置（向上浮动）
      const tmp = this.data[ind];
      this.data[ind] = this.data[Math.floor((ind - 1) / 2)];
      this.data[Math.floor((ind - 1) / 2)] = tmp;
      // 更新自身节点
      ind = Math.floor((ind - 1) / 2); // 更新当前值所在下标
    }
    console.info(this.data)
    return this.data;
  }
  /** 删除
   * 删除第一个值，把最后的位置和第一个替换。tail前移一位。调整
   */
  pop() {
    if (this.cnt == 0) return;
    [this.data[0], this.data[this.cnt - 1]] = [this.data[this.cnt - 1], this.data[0]];
    this.cnt--;
    let ind = 0;
    let n = this.cnt - 1;
    while(ind * 2 + 1 <= n) { // 下标有；ind * 2 + 1 是左子树。这里判断条件是有孩子节点
      let tmp = ind; // 用于比较和记录当前节点、左子节点、右子节点哪个最大的下标
      if (this.data[tmp] < this.data[ind * 2 + 1]) tmp = ind * 2 + 1; // 左节点比较
      if (ind * 2 + 2 <= n && this.data[tmp] < this.data[ind * 2 + 2]) tmp = ind * 2 + 2; // 右节点比较
      if (tmp == ind) break;
      [this.data[tmp], this.data[ind]] = [this.data[ind], this.data[tmp]]
      ind = tmp
    }
    console.info(this.data)
    return this.data;
  }
}

const heap1 = new Heap();
heap1.push(6)
heap1.push(5)
heap1.push(0)
heap1.push(2)
heap1.pop();



// 小顶堆
class Heap2 {
  constructor() {
      this.data = [];
      this.tail = 0;
  }
  top() {
      return this.data[0];
  }
  size() {
      return this.tail;
  }
  push(val) {
     this.data[this.tail++] = val;
     let ind = this.tail - 1;
     while(ind && this.data[ind] < this.data[Math.floor((ind - 1) / 2)]) {
          const temp = this.data[ind];
          this.data[ind] = this.data[Math.floor((ind - 1) / 2)];
          this.data[Math.floor((ind - 1) / 2)] = temp;
         ind = Math.floor((ind - 1) / 2);
     }
     console.info("push", this.data, val)
     return;
  }
  pop() {
     if(this.tail == 0) return;
     this.data[0] = this.data[this.tail - 1];
     this.data.pop()
     this.tail--;
     let n = this.tail - 1;
     let ind = 0;
     while(ind * 2 + 1 <= n) { // 有左子，就是有子
         let temp = ind;
         if (this.data[ind] > this.data[ind * 2 + 1]) temp = ind * 2 + 1;
         if (ind * 2 + 2 <= n && this.data[temp] > this.data[ind * 2 + 2]) temp = ind * 2 + 2;
         if (ind == temp) break;
         [this.data[temp], this.data[ind]] = [this.data[ind], this.data[temp]]
         ind = temp
     }
     console.info("pop", this.data, this.tail)
     return;
  }
}
// const heap = new Heap2();
// heap.push(12)
// heap.push(3)
// heap.push(13)
// heap.pop();
// heap.push(33)
// heap.push(0)
// heap.push(0)
// heap.pop();
// heap.push(32)
// heap.push(38)
// heap.pop();






console.info([6,10,2,6,5,0,6,3,1,0,0].sort((a, b) => b - a))





